package leetcode_core.leetcode_1;

import org.junit.Test;

public class LongestPalindromeSubseq {
    public int longestPalindromeSubseq(String s) {
        //对于动态规划问题,我们三步走
        //1.定义dp数组,dp[i][j]指的是arr[i...j]之间其回文子序列长度为dp[i][j]
        int[][] dp = new int[s.length()+5][s.length()+5];
        //2.写出base-case
        for(int i = 0 ;i<s.length();i++){
            dp[i][i] = 1;
        }
        //3.写出状态转移方程
        for(int i = s.length()-2;i>=0;i--){
            for(int j = i+1;j<s.length();j++){
                if(s.charAt(i)== s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1]+2;
                }else{
                    dp[i][j] = Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][s.length()-1];
    }

    @Test
    public void test(){
        System.out.println(longestPalindromeSubseq("bbbab"));
        System.out.println(longestPalindromeSubseq("cbbd"));
    }
}
